package com.imooc.distributedemo.resume.leetcode;

/**
 * leetcode05 最长回文字符串
 */
public class Solution05 {
    public static void main(String[] args) {
        String s = "abddeeaccc";
        String result = longestPalindrome(s);
        System.out.println(result);
    }

    public static String longestPalindrome(String s) {
        int len=s.length();
        int left=0,right=0,res=0;//记录左右边界和右-左的长度
        boolean[][] dp=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){//j=i这步就将每个单个字符dp赋为了true
                if(s.charAt(i)==s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])){//如果j - i <= 1，必是回文串
                    dp[i][j] = true;
                    if(j-i>res){
                        res=j-i;//res记得也得更新！
                        left=i;
                        right=j;
                    }
                }
            }
        }
        return s.substring(left,right+1);//左闭右开
    }
}
